package com.zjsru.oneDay202210;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author: CookLee
 * @Date: 2022/10/9
 *
 * 括号的分数
 * () 得 1 分。
 * AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
 * (A) 得 2 * A 分，其中 A 是平衡括号字符串。
 *
 * 输入： "()"
 * 输出： 1
 *
 * 输入： "(())"
 * 输出： 2
 *
 * 输入： "(()(()))"
 * 输出： 6
 */
public class ScoreOfParentheses {
    
    /**
     * 栈顶元素 cur = 0，即当前的 ) 的前一元素就是 ( ，根据 () 得一分的规则可知，我们本次操作得到的分值为 11；
     * 栈顶元素 cur!= 0 cur=0，即当前 ) 与其匹配的 (
     * 中间相隔了其他字符，根据 (A) 的得分规则，此时可知得分为 cur×2；
     */
    public int scoreOfParentheses(String s) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addLast(0);
        for (char c : s.toCharArray()) {
            if (c == '(') {
                deque.addLast(0);
            } else {
                int cur = deque.pollLast();
                // A + B => 子平衡括号字符串 A 是空串，(A) 的分数为 1，否则 (A) 的分数为 2*cur
                deque.addLast(deque.pollLast() + Math.max(cur * 2, 1));
            }
        }
        return deque.peekLast();
    }
    
    /**
     * 分治
     * */
    public int scoreOfParentheses2(String s) {
        if (s.length() == 2) {
            return 1;
        }
        int bal = 0, n = s.length(), len = 0;
        for (int i = 0; i < n; i++) {
            bal += (s.charAt(i) == '(' ? 1 : -1);
            if (bal == 0) {
                len = i + 1;
                break;
            }
        }
        if (len == n) {
            return 2 * scoreOfParentheses(s.substring(1, n - 1));
        } else {
            return scoreOfParentheses(s.substring(0, len)) + scoreOfParentheses(s.substring(len));
        }
    }
    
    public static void main(String[] args) {
        ScoreOfParentheses scoreOfParentheses = new ScoreOfParentheses();
        String s = "(()(()))";
        System.out.println(scoreOfParentheses.scoreOfParentheses(s));
    }
}
